package q127_ladderLength;

import java.util.*;

public class Solution_2 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        Set<String> visited = new HashSet<>();
        Set<String> cnt = new HashSet<>(wordList);

        if (!cnt.contains(endWord)) {
            return 0;
        }
        int[] charNums = new int[26];
        // 统计beginWord中每一个字符的个数
//        for (int i = 0; i < beginWord.length(); i++) {
//            charNums[beginWord.charAt(i) - 'a']++;
//        }
        Queue<String> queue = new LinkedList<>();
        // 首先压入start
        queue.offer(beginWord);
        // visited用来保存哪些组合已经出现
        visited.add(beginWord);
        // 记录变化步数
        // 这里要用2开始 因为开头的begin和end也要算进去 所以要加2
        int step = 2;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                // 依次取出queue中元素
                String curr = queue.poll();
                for (int j = 0; j < curr.length(); j++) {
                    for (int k = 0; k < 26; k++) {
                        StringBuilder sb = new StringBuilder(curr);
                        if ((char) ('a' + k) != curr.charAt(j)) {
                            sb.setCharAt(j, (char) ('a' + k));
                            String next = sb.toString();
                            if (!visited.contains(next) && cnt.contains(next)) {
                                if (next.equals(endWord)) {
                                    return step;
                                }
                                queue.offer(next);
                                visited.add(next);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return 0;
    }
}
